White's Studio.

LintCode-91. Minimum Adjustment Cost

LintCode
2018/08/24 Share

LintCode-91. Minimum Adjustment Cost

91. Minimum Adjustment Cost

Description

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

You can assume each number in the array is a positive integer and not greater than 100.

Example

Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it’s minimal.

Return 2.

Analyst:

题目：对 A[i]进行调整, A[i] -> B[i]，

使得：

  1. | B[i] - B[i-1] |<= target
  2. Sum{|A[i] - B[i]|}值最小， 求最小Sum{|A[i] - B[i]|}

  1. 最后一步：

    F[k]表示到 第k-1个数的总调整数 result 。

    1）需要调整，调整总和 F[k] = F[k-1] + min (A[k] + target - A[k-1] || A[k] - target - B[k-1] ) ) ( |A[k] - B[k-1]| > target )

    2) 不需要调整， F[k] = F[k-1] ( |A[k] - A[k-1]| <= target )

    因为这里用到调整后的A[k-1],我们把 A[k-1]记做 m 保存在 A[k][m]上，表示每当我们走到A[k-1]，并且吧这个数变成了 m

    因此，以上式子变成F[k][m]表示，走到A[k-1]时， 把A[k-1]变成 m 是的总调整数

    F[k][m] = min (F[k][m], F[k-1][n] + abs(A[k-1]- m))

  2. 顺序从小到大

  3. 初始状态, 边界情况

    F[1][j] = 0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    public int MinAdjustmentCost(List<Integer> A, int target) {
        // write your code here
        int len = A.size();
        int max = 100;
        int[][] F = new int[len+1][max+1];
        
        if (len == 0) 
            return 0;
            
        
        
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <=max; j++) {
                F[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for (int i = 0; i <= max; i++) {
            F[1][i] = Math.abs(i-A.get(0));
        }
        
        for (int i = 2; i <= len; i++) {
            for (int j = 0; j <= max; j++) {
                for (int k = 0; k <= max; k++) {
                    if ( Math.abs(k - j ) <= target ) {
                        // System.out.println("===================== " + " i is " + i + "  last min is " + F[i][j] + "  " +  Math.abs(A.get(i-1) - j)  + "   " + F[i-1][k] );
                        // System.out.println(F[i][j]);
                        F[i][j] = Math.min(F[i][j], F[i-1][k] + Math.abs(A.get(i-1) - j) );
                    }
                }
                
            }
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 0; i <= max; i++) {
            if (F[len][i] == 0) 
            System.out.println("===================== " + i );
            result = Math.min(result, F[len][i]);
        }
        return result;
    }
}

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/08/24/LintCode-91. Minimum Adjustment Cost/

发表日期: August 24th 2018, 1:22:18

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. LintCode-91. Minimum Adjustment Cost
    1. 1.0.1. Description
    2. 1.0.2. Example
    3. 1.0.3. Analyst:
    4. 1.0.4. Code
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm